package problems.daily;

/**
 * 1802. 有界数组中指定下标处的最大值
 * <p>https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/</p>
 *
 * @author habitplus
 * @since 9:51, 2023/1/4
 */
public class DT1802 {
    public int maxValue(int n, int index, int maxSum) {
        int left = 1;
        int right = maxSum;
        int mid;

        while (left < right) {
            mid = (left + right + 1) / 2;
            if (valid(mid, n, index, maxSum)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private boolean valid(int mid, int n, int l, int maxSum) {
        int r = n - l - 1;
        return mid + cal(mid, l) + cal(mid, r) <= maxSum;
    }

    private long cal(int big, int length) {
        if (length + 1 < big) {
            int small = big - length;
            return (long) (big - 1 + small) * length / 2;
        } else {
            int ones = length - (big - 1);
            return (long) big * (big - 1) / 2 + ones;
        }
    }
}
